package tp1;

public class TrieurListeForme {

	public enum SorteTri {
		Aucun, 
		NSEQCroissant, 
		NSEQDecroissant, 
		AireCroissant, 
		AireDecroissant, 
		DistanceMaxCroissant, 
		DistanceMaxDecroissant, 
		TypeFormeCroissant, 
		TypeFormeDecroisstant
	}

	/**Tri la liste selon le type de tri voulu
	 * @param liste Liste à trier
	 * @param tri Sorte de tri
	 * @return La liste trié
	 */
	public ListeChainee<Forme> trierListe(ListeChainee<Forme> liste, SorteTri tri) {
		System.out.println("Liste à trier");
		System.out.println(afficherListe(liste));
		return trier(liste, tri);
	}

	/**Sépare la liste en deux jusqu'à ce qu'il n'en reste qu'un et le compare avec la deuxieme item
	 * @param liste Liste à trier
	 * @param tri Sorte de tri
	 * @return Liste triée
	 */
	private ListeChainee<Forme> trier(ListeChainee<Forme> liste, SorteTri tri) {
		ListeChainee<Forme> listeTempo1 = new ListeChainee<Forme>();
		ListeChainee<Forme> listeTempo2 = new ListeChainee<Forme>();

		int largeur = liste.obtenirLargeur();

		if (largeur == 0) {
			return new ListeChainee<Forme>();
		} else if (largeur == 1) {
			return liste;
		} else {
			for (int i = 0; i < largeur / 2; i++) {
				listeTempo1.ajouter(liste.sonder());
			}

			for (int i = (largeur / 2); i < largeur; i++) {
				listeTempo2.ajouter(liste.sonder());
			}
			System.out.println("Liste1");
			System.out.println(afficherListe(listeTempo1));
			System.out.println("Liste2");
			System.out.println(afficherListe(listeTempo2));
			listeTempo1 = trier(listeTempo1, tri);
			listeTempo2 = trier(listeTempo2, tri);
			return fusionner(listeTempo1, listeTempo2, tri);
		}
	}

	/**Compare les valeurs dans les deux listes et retourne une liste avec les valeurs triées
	 * @param liste1 Premiere liste à comparer
	 * @param liste2 Deuxieme liste à comparer
	 * @param tri Sorte de tri
	 * @return Liste triée
	 */
	private ListeChainee<Forme> fusionner(ListeChainee<Forme> liste1, ListeChainee<Forme> liste2, SorteTri tri) {
		switch (tri) {
			case NSEQCroissant:
				return trierNSeqCroissant(liste1, liste2);
			case NSEQDecroissant:
				return trierNSeqDecroissant(liste1, liste2);
			case AireCroissant:
				return trierAireCroissant(liste1, liste2);
			case AireDecroissant:
				return trierAireDecroissant(liste1, liste2);
			case DistanceMaxCroissant:
				return trierDistanceMaxCroissant(liste1, liste2);
			case DistanceMaxDecroissant:
				return trierDistanceMaxDecroissant(liste1, liste2);
			case TypeFormeCroissant:
				return trierTypeFormeCroissant(liste1, liste2);
			case TypeFormeDecroisstant:
				return trierTypeFormeDecroissant(liste1, liste2);
			default:
				return null; // Ne devrait pas se produire...
		}
	}

	/** Tri par NSEQ en ordre croissant
	 * @param liste1 Premiere liste à comparer
	 * @param liste2 Deuxieme liste à comparer
	 * @return Liste triée
	 */
	private ListeChainee<Forme> trierNSeqCroissant(ListeChainee<Forme> liste1, ListeChainee<Forme> liste2) {
		ListeChainee<Forme> resultat = new ListeChainee<Forme>();
		while (liste1.obtenirLargeur() > 0 || liste2.obtenirLargeur() > 0) {
			if (liste1.obtenirLargeur() == 0) {
				resultat.ajouter(liste2.sonder());
			} else if (liste2.obtenirLargeur() == 0) {
				resultat.ajouter(liste1.sonder());
			} else {
				if (((Forme) liste1.obtenirPremier()).obtenirNseq() <= ((Forme) liste2.obtenirPremier()).obtenirNseq()) {
					resultat.ajouter((Forme) liste1.sonder());
				} else {
					resultat.ajouter((Forme) liste2.sonder());
				}
			}
		}
		System.out.println(afficherListe(resultat));
		return resultat;
	}
	
	/** Tri par NSEQ en ordre décroissant
	 * @param liste1 Premiere liste à comparer
	 * @param liste2 Deuxieme liste à comparer
	 * @return Liste triée
	 */
	private ListeChainee<Forme> trierNSeqDecroissant(ListeChainee<Forme> liste1, ListeChainee<Forme> liste2) {
		ListeChainee<Forme> resultat = new ListeChainee<Forme>();
		while (liste1.obtenirLargeur() > 0 || liste2.obtenirLargeur() > 0) {
			if (liste1.obtenirLargeur() == 0) {
				resultat.ajouter(liste2.sonder());
			} else if (liste2.obtenirLargeur() == 0) {
				resultat.ajouter(liste1.sonder());
			} else {
				if (((Forme) liste1.obtenirPremier()).obtenirNseq() > ((Forme) liste2.obtenirPremier()).obtenirNseq()) {
					resultat.ajouter((Forme) liste1.sonder());
				} else {
					resultat.ajouter((Forme) liste2.sonder());
				}
			}
		}
		System.out.println(afficherListe(resultat));
		return resultat;
	}
	
	/** Tri par le type de forme en ordre croissant
	 * @param liste1 Premiere liste à comparer
	 * @param liste2 Deuxieme liste à comparer
	 * @return Liste triée
	 */
	private ListeChainee<Forme> trierTypeFormeCroissant(ListeChainee<Forme> liste1, ListeChainee<Forme> liste2) {
		ListeChainee<Forme> resultat = new ListeChainee<Forme>();

		while (liste1.obtenirLargeur() > 0 || liste2.obtenirLargeur() > 0) {
			if (liste1.obtenirLargeur() == 0)
				resultat.ajouter(liste2.sonder());
			else if (liste2.obtenirLargeur() == 0)
				resultat.ajouter(liste1.sonder());
			else {
				if (liste1.obtenirPremier().obtenirEntierTypeForme() <= liste2.obtenirPremier().obtenirEntierTypeForme())
					resultat.ajouter(liste1.sonder());
				else
					resultat.ajouter(liste2.sonder());
			}
		}
		System.out.println(afficherListe(resultat));
		return resultat;
	}
	
	/** Tri par le type de forme en ordre croissant
	 * @param liste1 Premiere liste à comparer
	 * @param liste2 Deuxieme liste à comparer
	 * @return Liste triée
	 */
	private ListeChainee<Forme> trierTypeFormeDecroissant(ListeChainee<Forme> liste1, ListeChainee<Forme> liste2) {
		ListeChainee<Forme> resultat = new ListeChainee<Forme>();

		while (liste1.obtenirLargeur() > 0 || liste2.obtenirLargeur() > 0) {
			if (liste1.obtenirLargeur() == 0)
				resultat.ajouter(liste2.sonder());
			else if (liste2.obtenirLargeur() == 0)
				resultat.ajouter(liste1.sonder());
			else {
				if (liste1.obtenirPremier().obtenirEntierTypeForme() > liste2.obtenirPremier().obtenirEntierTypeForme())
					resultat.ajouter(liste1.sonder());
				else
					resultat.ajouter(liste2.sonder());
			}
		}
		System.out.println(afficherListe(resultat));
		return resultat;
	}
	
	/** Tri par l'aire en ordre croissant
	 * @param liste1 Premiere liste à comparer
	 * @param liste2 Deuxieme liste à comparer
	 * @return Liste triée
	 */
	private ListeChainee<Forme> trierAireCroissant(ListeChainee<Forme> liste1, ListeChainee<Forme> liste2) {
		ListeChainee<Forme> resultat = new ListeChainee<Forme>();

		while (liste1.obtenirLargeur() > 0 || liste2.obtenirLargeur() > 0) {
			if (liste1.obtenirLargeur() == 0)
				resultat.ajouter(liste2.sonder());
			else if (liste2.obtenirLargeur() == 0)
				resultat.ajouter(liste1.sonder());
			else {
				if (liste1.obtenirPremier().calcAire() <= liste2.obtenirPremier().calcAire())
					resultat.ajouter(liste1.sonder());
				else
					resultat.ajouter(liste2.sonder());
			}
		}
		System.out.println("Par aire croissant : " + afficherListe(resultat));
		return resultat;
	}
	
	/** Tri par l'aire en ordre décroissant
	 * @param liste1 Premiere liste à comparer
	 * @param liste2 Deuxieme liste à comparer
	 * @return Liste triée
	 */
	private ListeChainee<Forme> trierAireDecroissant(ListeChainee<Forme> liste1, ListeChainee<Forme> liste2) {
		ListeChainee<Forme> resultat = new ListeChainee<Forme>();

		while (liste1.obtenirLargeur() > 0 || liste2.obtenirLargeur() > 0) {
			if (liste1.obtenirLargeur() == 0)
				resultat.ajouter(liste2.sonder());
			else if (liste2.obtenirLargeur() == 0)
				resultat.ajouter(liste1.sonder());
			else {
				if (liste1.obtenirPremier().calcAire() > liste2.obtenirPremier().calcAire())
					resultat.ajouter(liste1.sonder());
				else
					resultat.ajouter(liste2.sonder());
			}
		}
		System.out.println("Par aire decroissant : " + afficherListe(resultat));
		return resultat;
	}
	
	/** Tri par la distance maximal en ordre croissant
	 * @param liste1 Premiere liste à comparer
	 * @param liste2 Deuxieme liste à comparer
	 * @return Liste triée
	 */
	private ListeChainee<Forme> trierDistanceMaxCroissant(ListeChainee<Forme> liste1, ListeChainee<Forme> liste2) {
		ListeChainee<Forme> resultat = new ListeChainee<Forme>();

		while (liste1.obtenirLargeur() > 0 || liste2.obtenirLargeur() > 0) {
			if (liste1.obtenirLargeur() == 0)
				resultat.ajouter(liste2.sonder());
			else if (liste2.obtenirLargeur() == 0)
				resultat.ajouter(liste1.sonder());
			else {
				if (liste1.obtenirPremier().calcDistanceMax() <= liste2.obtenirPremier().calcDistanceMax())
					resultat.ajouter(liste1.sonder());
				else
					resultat.ajouter(liste2.sonder());
			}
		}
		System.out.println("Par distance max croissant : " + afficherListe(resultat));
		return resultat;
	}
	
	/** Tri par la distance maximal en ordre décroissant
	 * @param liste1 Premiere liste à comparer
	 * @param liste2 Deuxieme liste à comparer
	 * @return Liste triée
	 */
	private ListeChainee<Forme> trierDistanceMaxDecroissant(ListeChainee<Forme> liste1, ListeChainee<Forme> liste2) {
		ListeChainee<Forme> resultat = new ListeChainee<Forme>();

		while (liste1.obtenirLargeur() > 0 || liste2.obtenirLargeur() > 0) {
			if (liste1.obtenirLargeur() == 0)
				resultat.ajouter(liste2.sonder());
			else if (liste2.obtenirLargeur() == 0)
				resultat.ajouter(liste1.sonder());
			else {
				if (liste1.obtenirPremier().calcDistanceMax() > liste2.obtenirPremier().calcDistanceMax())
					resultat.ajouter(liste1.sonder());
				else
					resultat.ajouter(liste2.sonder());
			}
		}
		System.out.println("Par distance max decroissant : " + afficherListe(resultat));
		return resultat;
	}

	/**
	 * Pour debugger
	 * 
	 * @param liste
	 * @return Une chaine montrant les nseq des formes dans la liste
	 */
	private String afficherListe(ListeChainee<Forme> liste) {
		String chaine = "";
		for (int i = 0; i < liste.obtenirLargeur(); i++) {
			chaine += liste.obtenir(i).calcDistanceMax() + " <||> ";
		}
		return chaine;
	}
}
